package toOffer;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/19 17:11
 * @description <p>数组中和为 0 的 3 个数字</p>
 */

/**
 * 题目：输入一个数组，如何找出数组中所有和为 0 的 3 个数字的三元组？
 * 需要注意的是，返回值中不得包含重复的三元组。
 * 例如，在数组[-1, 0, 1, 2, -1, -4]中有两个三元组的和为 0，它们分别是[-1, 0, 1]和[-1, -1, 2]。
 */
public class toOffer2_2_7 {

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum(nums);

        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.print(integer + " ");

            }
            System.out.println();
        }
    }

    /**
     * 两种情况：
     * （1）数组是已经排好序的，可以先指定数组中的一个数k，然后快慢指针查找数组里、是否存在其他两个值加起来等于-k的数
     * （2）数组是无序的，要先进行排序，排好顺序之后再进行上面的操作
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        //先排序
        List<Integer> list = Arrays.stream(nums).sorted().boxed().collect(Collectors.toList());
        //从第一个数开始遍历list数组选取一个数k，再选取k这个数之后的数组进行左右指针的查找
        for (int i = 0; i < list.size(); i++) {
            if (i != 0 && Objects.equals(list.get(i), list.get(i - 1))) {
                continue;
            }
            List<List<Integer>> funList = fun(list.subList(i + 1, list.size()), list.get(i));
            if (funList.size() != 0) {
                resultList.addAll(funList);
            }
        }
        return resultList;
    }

    /**
     * 进行快慢指针的查找操作
     *
     * @param list
     * @param k
     * @return
     */
    public static List<List<Integer>> fun(List<Integer> list, Integer k) {
        List<List<Integer>> newList = new ArrayList<>();
        //构造快慢指针
        Integer slow = 0;
        Integer fast = list.size() - 1;

        //主体判断
        while (slow < fast) {

            Integer sum = list.get(slow) + list.get(fast);
            if (sum < -k) {
                slow++;
            }
            if (sum > -k) {
                fast--;
            }
            if (sum.equals(-k)) {
                if (slow != 0 && list.get(slow).equals(list.get(slow - 1))) {
                    slow++;
                    continue;
                }
                newList.add(Arrays.asList(list.get(slow), list.get(fast), k));
                slow++;
            }
        }
        return newList;
    }
}
